#!/usr/bin/python

from node import Node

def sum_to_deepest(root):
    '''Returns the sum of the deepest leaf of the tree defined by Node root.
    If there are multiple deepest leafs, returns the greatest sum between
    them.'''
    
    if root:
        sums, depths = populate_sums(root)
        deepest_sums = [sum for sum, depth in zip(sums, depths) \
                        if depth == max(depths)]
        largest_sum = max(deepest_sums)
        return largest_sum
    else:
        return 0

def populate_sums(root):
    '''Populates a list of different sums and their respective depths.
    Returns two lists, one of sums and another of depths.'''
    sums = []
    depths = []
    
    sum = root.key if root else 0
    depth = 0
    
    while root.left != None:
        root = root.left
        sum += root.key
    